#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
using namespace std;

const ll N = 1e6 + 10, INF = 0x3f3f3f3f;

ll n, m, k;
struct node { ll u, v, w, id; };
vector<node> edge;

ll f[N];
ll find(ll x) { return x != f[x] ? f[x] = find(f[x]) : f[x]; }

void solve()
{
    edge.clear();
    cin >> n >> m >> k;
    for (ll i = 0;i <= n;i++) f[i] = i;
    for (ll i = 1;i <= m;i++) {
        ll u, v, w; cin >> u >> v >> w;
        edge.push_back({ u,v,w ,i });
    }
    sort(edge.begin(), edge.end(), [](node a, node b) {return a.w < b.w;});

    vector<ll> id;
    ll cnt = 0, sum = 0;
    for (ll i = 0;i < m;i++) {
        auto [u, v, w, idx] = edge[i];
        if (u == v || find(u) == find(v)) continue;
        if (cnt < n - 1 - k || w <= 1) {
            sum += w;
            id.push_back(idx);
            f[find(u)] = find(v);
            cnt++;
        }
    }

    vector<pair<ll, ll>> ans;
    cnt = 0;
    for (ll i = 1;i < n;i++) {
        if (find(i) == find(i + 1)) continue;
        sum++;
        id.push_back(++cnt + m);
        ans.push_back({ i,i + 1 });
        f[find(i)] = find(i + 1);
    }

    cout << ans.size() << "\n";
    for (ll i = 0;i < ans.size();i++)
        cout << ans[i].first << ' ' << ans[i].second << '\n';
    cout << sum << "\n";
    for (ll i = 0;i < id.size();i++)
        cout << id[i] << ' ';
    cout << "\n";
}

signed main()
{
    // ios::sync_with_stdio(0);
    // cin.tie(0);cout.tie(0);
    // #define ONLINE_JUDGE
#ifndef ONLINE_JUDGE
    std::istringstream in(R"()");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll T = 1;
    cin >> T;
    for (ll i = 1;i <= T;i++) {
        solve();
    }
}